Within most computer systems, a central processing unit (CPU) is connected to cache memory. Cache memory can be quickly accessed by the CPU. As a result, data can be stored in or retrieved from cache memory much faster than the same data could be stored in or retrieved from various other storage media coupled to the CPU. Cache memory is located within a cache memory unit comprised of computer system hardware (e.g., random access memory (RAM), read only memory (ROM), busses, logic components, etc.). Data in a cache memory is organized in "lines". A cache line is the addressable entity of a cache memory.
A cache memory unit within a computer system gains several benefits when a portion of the cache address, the cache tag, is minimized (i.e., shortened). With a short cache tag width, the cache memory unit is less expensive to produce, requires smaller components to implement, generates less heat, and weighs less than a cache memory unit using a larger cache tag width.
Prior Art FIG. 1 is a schematic illustration of 4 gigabytes (GB) of addressable memory space 100. Additionally, the cache memory chunk 102 employed in the embodiment of Prior Art FIG. 1 has a total size of 256 kilobytes (KB). In order to access data within 4 GB of addressable space 100, a 32-bit address is required. Equation 1 below is used to determine the cache tag width conventionally required to address a particular location of data within the large cacheable space, when a direct-mapped cache is used. Although the following discussion is limited to direct-mapped cache for purposes of clarity, the present invention is also well suited to use with fully set associative, or various other cache configurations. EQU log.sub.2 (cacheable space/cache size)=cache tag width (1)
As shown above, Equation 1 divides the total amount of cacheable space by the cache size. After the division, the resultant value is then logged by base 2. Inserting the values for Prior Art FIG. 1 into Equation 1 produces the resultant expression and value: EQU log.sub.2 (4 GB/256 KB)=14.
Thus, in the embodiment of Prior Art FIG. 1 the cache tag must be 14 bits wide for a CPU to reconstruct the full 32-bit address necessary to identify a cache line within 4 GB contiguous cacheable space 100.
In order to shorten the cache tag width, attempts have been made to reduce the size of the cacheable space. Prior Art FIG. 2 illustrates a prior-art approach wherein only 256 megabytes (MB) of the 4 GB of total addressable space 200 are cacheable space 204. That is, the cacheable space extending from 256 MB to 4 GB is non-cacheable space 202. As a result, a shorter tag width can be used to locate a particular chunk of cache within the 256 MB of cacheable space 204. More specifically, given 256 MB of cacheable space 204 and a 256 KB cache memory 206, Equation 1 produces the resultant expression and value: EQU log.sub.2 (256 MB/256 KB)=10.
Hence, in the embodiment of Prior Art FIG. 2 the cache tag need only be 10 bits wide for the CPU to reconstruct the 28-bit address necessary to identify a cache line within the 256 MB of cacheable space 204. Therefore, by reducing the size of the addressable space from 4 GB to 256 MB, the cache tag width is decreased from 14 bits to 10 bits. Although this prior-art method of reducing the cacheable space decreases the width of the cache tag, such a prior-art approach is only useful when the cacheable space is contiguous.
When the cacheable space is discontiguously-arranged throughout the addressable space, the cache tag width cannot be minimized using prior-art methods. A typical prior-art method of caching data within discontiguously-arranged cacheable space requires two steps. First, the total amount of memory locations between, and including, the lowest cacheable address location and the highest cacheable address location is calculated in such a way that the size if this total amount of memory is a power of two and is aligned to a multiple of its size. Second, the resultant value of the first step is inserted into the cacheable space variable of Equation 1. Equation 1 calculates how many bits the cache tag must contain for the CPU to reconstruct the address necessary to identify a cache line within the discontiguously-arranged cacheable space.
As an example, Prior Art FIG. 3 schematically illustrates discontiguously-arranged cacheable space located within 4 GB of addressable space 300. The embodiment of Prior Art FIG. 3 includes a 256 KB cache memory 301. Addressable space 300 includes a total of 256 MB of cacheable space comprised of 16 MB of cacheable ROM cache space 302 and 240 MB of cacheable RAM cache space 304. The addressable space 300 further includes unused cacheable space 306. As shown in Prior Art FIG. 3, 16 MB of cacheable ROM cache space 302 is located at the highest address of 4 GB of addressable space 300, whereas the 240 MB of cacheable RAM cache space 304 is located at the lowest address of 4 GB of cacheable space 300. Thus, in order to reconstruct the address of a particular cache line within such a discontiguous configuration, typical prior-art methods first determine the amount of memory locations between, and including, the lowest cacheable address and the highest cacheable address. Hence, in the embodiment of Prior Art FIG. 3, a total of 4 GB of memory locations must be cached. The second step of the typical prior-art method is to insert the 4 GB memory location value into the cacheable space variable of Equation 1. This value is then divided by the 256 KB cache memory 301, which produces the resultant expression and value: EQU log.sub.2 (4 GB/256 KB)=14.
Therefore, a discontiguously-arranged cacheable space requires a 14 bit cache tag width to locate a particular cache line, even though the addressable space is only 256 MB in size. As described above, a total contiguously arranged cacheable space of 256 MB only requires a 10 bit cache tag width to address any particular chunk of cache.
Requiring longer cache tag widths results in a cache memory unit which is more expensive to produce, generates more heat, requires greater real estate, and is heavier than a cache memory unit with a shorter cache tag width. Therefore, it would be advantageous to provide a method for caching discontiguous memory address spaces with shorter cache tags.